/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.LinkedList;
import java.util.Queue;

import com.gwcloud.leetcode.common.datastructure.Node;

/**
 * @ClassName   : Leetcode0116 
 * @author      : ganwei 
 * @date        : 2020年5月26日
 * @Description : Leetcode0116 填充每个节点的下一个右侧节点指针
 */
public class Leetcode0116 {
    /**
     * -解题思路,广度优先遍历
     */
	public Node connect(Node root) {
		if(root == null){
			return null;
		}
		Queue<Node> q = new LinkedList<Node>();
		q.offer(root);
		
		while(!q.isEmpty()){
			int length = q.size();
			Node left = null;
			for(int i = 0; i < length; i++){
				Node n = q.poll();
				
				if(left == null){
					left = n;
				}else{
					left.next = n;
					left = n;
				}
				
				if(n.left != null){
					q.offer(n.left);
				}
				if(n.right != null){
					q.offer(n.right);
				}
			}
		}
		
        return root;
    }
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
